package DP;

import org.junit.Test;

import java.util.Arrays;

/**
 * @BelongsProject: SeniorArchitect-LeetCode
 * @BelongsPackage: DP
 * @Author: zhuangxiaoyan
 * @CreateTime: 2023-10-22  16:53
 * @Description: TODO
 * @Version: 1.0
 */
public class 整数拆分343 {
    // dp[i] 表示的i 拆分后的最大数字的乘积
    // dp[i]=Max(j*(i-j)，j*dp[i-j])
    // dp[0]=0,dp[1]=0 dp[2]=1
    // for (i=3;i<=n;i++)
    //  for(int j=1；j<i；j++){dp[i]=Max(j*(i-j)，j*dp[i-j])}

    public int integerBreak(int n) {
        int[] dp = new int[n + 1];
        dp[1]=0;
        dp[2]=1;
        for (int i = 3; i <= n; i++) {
            // 记录每次拆分乘积的结果 然后赋值给curmax
            int curMax = 0;
            for (int j = 1; j < i; j++) {
                curMax = Math.max(curMax, Math.max(j * (i - j), j * dp[i - j]));
            }
            dp[i] = curMax;
        }
        System.out.println(Arrays.toString(dp));
        return dp[n];
    }


    @Test
    public void test(){
        int i = integerBreak(10);
    }
}
